/**************************************************************************
* File:            search.h                                               *
* Description:     Abstract class Visitor, DFS, BFS                       *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/


#pragma once

#include "graph.h"
#include <memory>
#include <queue>
#include <vector>
#include <stack>

class Visitor{
public:
	virtual void enterVertex(int vertex) = 0;
	virtual void enterEdge(int from, int to) = 0;
	virtual void leaveEdge(int from, int to) = 0;
	virtual void leaveVertex(int vertex) = 0;
};

void BFS(int start, Graph const * graph, Visitor *visitor){
	std::queue<int> queue;
	std::vector<int> visited(graph->getVerticesNumber());

	queue.push(start);
	visited[start] = true;
	visitor->enterVertex(start);
	
	while (!queue.empty()){
		int vertex = queue.front();
		queue.pop();
		
		std::vector<int> incidenceList = graph->getIncidenceList(vertex);

		for (auto &to:incidenceList)
		if (!visited[to]){
			visited[to] = true;
			visitor->enterEdge(vertex, to);
			visitor->enterVertex(to);
			queue.push(to);
		}

		visitor->leaveVertex(vertex);
	}
}

/*recursive implementation*/
void DFS(int vertex, Graph const * graph, Visitor *visitor, std::vector<bool> &visited){
	visited[vertex] = true;
	visitor->enterVertex(vertex);
	
	std::vector<int> incident = graph->getIncidenceList(vertex);
	for (int &to : incident){
		visitor->enterEdge(vertex, to);
		if (!visited[to]){
			DFS(to, graph, visitor, visited);
			visitor->leaveEdge(vertex, to);
		}
	}

	visitor->leaveVertex(vertex);
}
	
void runDFS(Graph const * graph, Visitor * visitor, std::vector<int> order = std::vector<int>(0)){
	std::vector<bool> visited(graph->getVerticesNumber());
	if (order.size() == 0){
		for (int vertex = 0; vertex < graph->getVerticesNumber(); ++vertex)
		if (!visited[vertex])
			DFS(vertex, graph, visitor, visited);
	}
	else{
		for (int vertex:order)
		if (!visited[vertex])
			DFS(vertex, graph, visitor, visited);
	}
}
